Object-oriented computer programming languages such as JAVA and C# typically employ type hierarchies. In computer languages, types are used to describe a given entity. For example, a computer language may employ a data structure having various fields used to describe the subject type. The information contained within the fields uniquely defines the type. In object-oriented languages types have hierarchy, i.e., one type can be a subtype or supertype of another, e.g., type “apple” is a subtype of type “fruit”, and is a supertype of type “red apple”. Once the type is determined for some data in computer memory, it may be necessary to determine whether that type is a subtype of another type. Consider a type hierarchy for type T in which T has a subtype T′ and T′ has a subtype T″. It is known at compile time that T′ is of type T and that T″ is of type T′ and thus of type T. At run time it may be necessary to determine if an object of type T is actually of type T″. For example, at compile time it is known that all apples are fruit and that all red apples are apples and fruits. At run time a program may need to determine if an object of type apple is actually an object of type red apple. This type checking is a very common operation in object-oriented languages. Type checking may be accomplished through use of instructions at runtime, e.g., in virtual machines.
One method of dynamic type checking is to implement, within each object, a field that points to a data structure that identifies the object type. That is, all objects of a given type will point to the same data structure. The data structure is metadata (data pertaining to data) for objects of that type. The data structure reflects the type hierarchy, so each data structure contains a field that points to its supertype. For example, for an object of type apple, the object will contain a field pointing to the metadata for its supertype, namely fruit. Therefore, to determine if an object is of a given type at runtime, the metadata for the object is examined and then successive supertypes are examined by traversing the type hierarchy. The supertype pointer at each data structure is dereferenced to obtain the next successive supertype. In general, the process is continued recursively until it is determined that a given type is a subtype of another type or until a root type is reached. This type of dynamic type checking algorithm is referred to as a linked data structure dynamic type checking algorithm. Each time a supertype pointer is obtained and dereferenced the process requires memory access. Such recursive memory access taxes processing resources and is time consuming.
An alternative method of dynamic type checking is to create a type hierarchy array for each object type that assigns an index to each element indicating depth in the type hierarchy. The number indicates the depth of the node within the type hierarchy. For example, index 0 may be assigned to the root type, index 1 may be assigned to type fruit (a subtype of the root type), index 2 may be assigned to type apple, index 3 may be assigned to type red apple, and so on. Each object contains a pointer to the array that contains its type hierarchy data. At run time, when it is necessary to determine if an object is of a specific type, the type hierarchy array for the object is accessed and the appropriate index is evaluated. If the index does not contain the type in question, then the object is not an instance of that type. For example, the type hierarchy array is accessed to check whether an object of type fruit is of type apple. Index 2 (the index assigned to type apple) is evaluated, if index 2 contains type apple, then the object is of type apple. If index 2 is empty or contains some other type (e.g., orange), or the array does not have an index 2, then the object is not of type apple.
Although the type hierarchy array reduces the required processing due to recursive memory access it can only be implemented for a subset of type hierarchies. In languages such as JAVA and C#, type hierarchies may be of two types; class types and interface types. For classes, the types have only one supertype (a type may have numerous subtypes), yielding a tree structure for the type hierarchy. This allows the type hierarchy array, as discussed above, to be created. Interfaces, on the other hand may have multiple supertypes, yielding a directed acyclic graph (DAG) structure for the type hierarchy. That is, because a type may have more than one supertype, a given index for a type hierarchy array may not be determined. Additionally, because the size of the array is fixed, the technique does not work if the depth of the type hierarchy exceeds the size of the array.